package zisu.algorithm.algorithm.UnionFind;

public class UnionFind2 implements UnionFind {

    private int[] parent;

    public UnionFind2(int size){
        parent = new int[size];

        //初始化各个元素，并且各元素之间并没有交集。
        for(int i = 0; i<size;i++){
            parent[i] = i;
        }
    }

    @Override
    public boolean isConnected(int p, int q) {
        return false;
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot){
            return;
        }
        parent[pRoot] = qRoot;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    //返回p节点的根节点
    //查找过程，查找元素p所对应的集合编号
    //O(h)复杂度，h 为树的高度。
    public int find(int p){
        if(p<0 || p>parent.length){
            throw new IllegalArgumentException("p is out of bound");
        }

        //根节点的parent[p] 对应的就是它自己( parent[0] = 0 ,如果索引0 就是根节点。 )。
        while (p!=parent[p]){
            p = parent[p];
        }
        return p;
    }
}
